#include "junix.h"

template <typename ValueType=int>
struct Node {
	Node() : prev(NULL), next(NULL) { }
	Node(const ValueType& value):data(value), prev(NULL), next(NULL) { }

	ValueType data;
	Node<ValueType> *prev, *next;
};

template <
typename ValueType=int,
typename Cmp=std::less<ValueType>
>
class List {
	public:
		List() : head(NULL), tail(NULL) { }
		virtual ~List() { destroy(); }

		//list add
		void list_add(const ValueType& value) {
			Node<ValueType> *n = new Node<ValueType>(value);
			Node<ValueType> *q=head;
			Cmp cmp;

			if (!head) { //head is null(null list)
				head = n;
				tail = n;
				return ;
			}

			while (q && !cmp(value,q->data) ) {
				q = q->next;
			}

			if (q==head) { //insert new head
				n->prev = NULL;
				n->next = q;
				q->prev = n;

				head = n;
				return;
			}

			if (!q) { //insert new tail
				tail->next = n;
				n->prev = tail;
				n->next = NULL;

				tail = n;
			} else { //insert int the middle
				n->prev = q->prev;
				q->prev->next = n;
				n->next = q;
				q->prev = n;
			}
		}

		// destroy all node
		void destroy() {
			Node<ValueType> *p=head, *q;
			while (p) {
				q=p;
				p=p->next;
				delete q;
			}

			head = NULL;
			tail = NULL;
		}


		//delete node with date of value  from the list
		void list_del(const ValueType& value) {
			Node<ValueType> *p = head, *q;
			if (!head) return;

			while (p) {
				q = p;
				p = p->next;
				if (q->data==value) list_del(q);	
			}
		}

		//delete node form list
		void list_del(Node<ValueType> *node) {
			if (!node) return;//node is null

			if (node==head) { //delete head
				if (tail==head) tail=NULL; //alse is tail
				head = node->next;
				head->prev = NULL;
			} else if (node==tail) { //delete tail(not head)
				tail = node->prev;
				tail->next = NULL;
			} else {  //not head not tail
				node->prev->next = node->next;
				node->next->prev = node->prev;
			}

			delete node;
		}


		//walk
		void walk() {
			Node<ValueType> *p=head;
			while (p) {
				std::cout<<p->data<<" ";
				p = p->next;
			}
		}

	private:
		Node<ValueType> *head,*tail;
};


int main(int argc, char **argv)
{
	//int v[] = {1,3,4,9,6,2,8};
	List<> list;
	const int size =100;
	for (int i=0;i<size;i++) {
		list.list_add(rand()%size);
	}	   

	list.walk();
	std::cout<<std::endl;

	for (int i=80;i<size;i++)
		list.list_del(i);

	list.walk();
	std::cout<<std::endl;
}
